// this is to host the code inherited from blue 
#define _CRT_SECURE_NO_DEPRECATE
#include "tab1.h"  // tab0 and tab1 
#include "zhou.h"
extern char *gtypes[44];  
extern char *ggrids[44]; // defined later 
const int p3[6][3] = { { 0,1,2 }, { 0,2,1 }, { 1,0,2 }, { 1,2,0 }, { 2,0,1 }, { 2,1,0 } };
//extern byte Tblfirst0_8[512] ;
long long bluecount[5];
struct BLUE_grid {
      unsigned char cells[9][9];
      int boxmasks[9];
      int rowmasks[9];
      int colmasks[9];
}blue_grid0;

 struct BLUE_spot {
	  int ispot;
      int r;
      int c;
      int b;
	  int cell;
      int dmask;
 }blue_spots81[81];

int first_bit[512];
int box_table[9][9];


void Blue_setup_tables(char * mygang){
     for (int i = 1; i < 512; i++) {
         int mask = i;
         int bit = 0;
         while (!(mask & 1)) {
            ++bit;
            mask >>= 1;
         }
         first_bit[i] = bit;
      }
 
      for (int i = 0; i < 9; i++)
      for (int j = 0; j < 9; j++)
         box_table[i][j] = 3 * (i / 3) + (j / 3);
	 // initial value for blue_grid0
	  memset(&blue_grid0, 0, sizeof(blue_grid0));
	  for (int i = 0; i < 27; i++) {
         blue_grid0.cells[i / 9][i % 9] = mygang[i] - '0';
         blue_grid0.colmasks[i % 9] |= (1 << (mygang[i] - '0'));
      }
	  // initial value for blue_spots81[81]
	  for(int i=0;i<81;i++){
		  BLUE_spot & s=blue_spots81[i];
		  s.cell=i;
		  s.r = i / 9;
          s.c = i % 9;
          s.b = box_table[s.r][s.c];
	  }
}

struct gangster_data {
   int first_n_aut;
   int n_aut_count;   // 1st is identity map
   int first_g_aut;
   int g_aut_count;   // 1st is identity transformation
};

gangster_data gtd[44];

int g_aut_c_order[392][9];
byte g_aut_maps[392][10];
byte n_aut_maps[355][10];
byte grid[81]; // grid values 0_9
bool band_swap;
int patterns[1296][2];
int pattern_count;
bool p_flags[1296];

void Blue_setup44(){
   int next_g_aut = 0;
   int next_n_aut = 0;

   for (int n44 = 0; n44 < 44; n44++)
   { 
	   unsigned char band_data[9][3];
      {
         for (int i = 0; i < 9; i++)
         for (int j = 0; j < 3; j++)
            band_data[i][j] = gtypes[n44][3 * i + j] - '0';
      }

      gtd[n44].first_n_aut = next_n_aut;

      {
         int aut_count = 0;   // numeric only

         int col_p[3];
         for (col_p[0] = 0; col_p[0] < 6; col_p[0]++)
         for (col_p[1] = 0; col_p[1] < 6; col_p[1]++)
         for (col_p[2] = 0; col_p[2] < 6; col_p[2]++)
         {
            unsigned char map[10];
            map[0] = 0;
            {
               for (int i = 0; i < 3; i++)
               for (int j = 0; j < 3; j++)
                  map[band_data[i][j]] = band_data[i][p3[col_p[i]][j]];
            }
            bool ok = true;
             for (int i = 0; i < 9; i++)
            {
               unsigned char n0 = map[band_data[i][0]];
               unsigned char n1 = map[band_data[i][1]];
               unsigned char n2 = map[band_data[i][2]];
               if (n0 > n1) {
                  unsigned char n = n0;
                  n0 = n1;
                  n1 = n;
               }
               if (n0 > n2) {
                  unsigned char n = n0;
                  n0 = n2;
                  n2 = n;
               }
               if (n0 != band_data[i][0])
               {
                  ok = false;
                  break;
               }
               if (n1 > n2) {
                  unsigned char n = n1;
                  n1 = n2;
                  n2 = n;
               }
               if (n1 != band_data[i][1])
               {
                  ok = false;
                  break;
               }
               if (n2 != band_data[i][2])
               {
                  ok = false;
                  break;
               }
            }
            if (ok)
            {
               ++aut_count;
               memcpy(n_aut_maps[next_n_aut++], map, 10);
            }
         }

         gtd[n44].n_aut_count = aut_count;
      }

      gtd[n44].first_g_aut = next_g_aut;

      {
         int aut_count = 0;   // geometric + (one) numeric

         unsigned char map[10];
         map[0] = 0;

         int row_p[3];
         for (int band_p = 0; band_p < 6; band_p++)
         for (row_p[0] = 0; row_p[0] < 6; row_p[0]++)
         for (row_p[1] = 0; row_p[1] < 6; row_p[1]++)
         for (row_p[2] = 0; row_p[2] < 6; row_p[2]++)
         {
            int r_order[9];
            {
               for (int i = 0; i < 3; i++)
               for (int j = 0; j < 3; j++)
                  r_order[3 * i + j] = 3 * p3[band_p][i] + p3[row_p[i]][j];
            }

            bool found = false;

            int col_p[3];
            for (col_p[0] = 0; col_p[0] < 6; col_p[0]++)
            for (col_p[1] = 0; col_p[1] < 6; col_p[1]++)
            for (col_p[2] = 0; col_p[2] < 6; col_p[2]++)
            {
               {
                  for (int i = 0; i < 3; i++)
                  for (int j = 0; j < 3; j++)
                     map[band_data[r_order[i]][j]] = band_data[i][p3[col_p[i]][j]];
               }
               bool ok = true;
                for (int i = 0; i < 9; i++)
               {
                  unsigned char n0 = map[band_data[r_order[i]][0]];
                  unsigned char n1 = map[band_data[r_order[i]][1]];
                  unsigned char n2 = map[band_data[r_order[i]][2]];
                  if (n0 > n1) {
                     unsigned char n = n0;
                     n0 = n1;
                     n1 = n;
                  }
                  if (n0 > n2) {
                     unsigned char n = n0;
                     n0 = n2;
                     n2 = n;
                  }
                  if (n0 != band_data[i][0])
                  {
                     ok = false;
                     break;
                  }
                  if (n1 > n2) {
                     unsigned char n = n1;
                     n1 = n2;
                     n2 = n;
                  }
                  if (n1 != band_data[i][1])
                  {
                     ok = false;
                     break;
                  }
                  if (n2 != band_data[i][2])
                  {
                     ok = false;
                     break;
                  }
               }
               if (ok)
               {
                  found = true;
                  goto found;
               }
            }

found:         if (found)
            {
               ++aut_count;
               memcpy(g_aut_maps[next_g_aut], map, 10);
               memcpy(g_aut_c_order[next_g_aut++], r_order, sizeof(r_order));
            }
         }

         gtd[n44].g_aut_count = aut_count;
      }
   }
}

#define  MaxPatCells  20
#define  MaxNAutCount 216


void bp_handler(char *buf, int n44 ){// with progressive brute force 
    extern GAME  game[50];
	bluecount[1]++;
	gangster_data &gt = gtd[n44];
	BLUE_grid grid=blue_grid0;
	unsigned char * grcells=grid.cells[0];
    unsigned char *good_maps[MaxPatCells][MaxNAutCount - 1];
    int spot_maps[72][MaxPatCells];  // for rows permutations
  	int numbers[MaxPatCells];
	BLUE_spot spots[MaxPatCells],  *s = spots, *s_end;//,*s_lim;

	// added for a step by step check of automorphisms
    int good_map_count[MaxPatCells];
    good_map_count[0] = gt.n_aut_count - 1;
    for (int n = 0; n < good_map_count[0]; n++)
       good_maps[0][n] = n_aut_maps[gt.first_n_aut + n + 1];


	// build the table of given
	for (int i = 27,nn=0; i < 81; i++)      {
		if (buf[i] < '1' || buf[i] > '9')     continue;
		(*s) = blue_spots81[i];
		s->ispot=nn++;
         ++s;
      }
	int pat_cells = (int)(s - spots);
	// prepare data for possible rows permutatons
     int p_aut_count = 0;
       { int m[6];
          memset(m, 0, sizeof(m));
          for (int i = 0; i < pat_cells; i++) {
             m[spots[i].r - 3] |= (0x100 >> spots[i].c);
             buf[9 * spots[i].r + spots[i].c] = '1' + i;
          }
          for (int band_p = 0; band_p < 6; band_p++) {
             if (p3[band_p][2] != 2)   continue;
             for (int row_p1 = 0; row_p1 < 6; row_p1++)
             for (int row_p2 = 0; row_p2 < 6; row_p2++) {
                int row_order[6];
                if (m[row_order[0] = 3 * p3[band_p][0] + p3[row_p1][0]] != m[0]
                 || m[row_order[1] = 3 * p3[band_p][0] + p3[row_p1][1]] != m[1]
                 || m[row_order[2] = 3 * p3[band_p][0] + p3[row_p1][2]] != m[2]
                 || m[row_order[3] = 3 * p3[band_p][1] + p3[row_p2][0]] != m[3]
                 || m[row_order[4] = 3 * p3[band_p][1] + p3[row_p2][1]] != m[4]
                 || m[row_order[5] = 3 * p3[band_p][1] + p3[row_p2][2]] != m[5])
                   continue;
                for (int i = 0; i < pat_cells; i++)
                   spot_maps[p_aut_count][i]
                      = buf[9 * (3 + row_order[spots[i].r - 3]) + spots[i].c] - '1';
                ++p_aut_count;
             }
          }
       }
	// start now the puzzles generation
 	s = spots;
	s_end=spots + pat_cells;

next_spot:   {
	int mask = grid.rowmasks[s->r]
         | grid.colmasks[s->c]
         | grid.boxmasks[s->b];
	mask = 511 & ~(mask >> 1);
	if (!mask)         goto backtrack;
	s->dmask = mask;
   }
next_value:   
	int ispot=s->ispot,gspot=ispot+1;
	
	{
      int number = first_bit[s->dmask] + 1;
      s->dmask &= (s->dmask - 1); // clear the bit 
      numbers[ispot] = number;
      grcells[s->cell] = number;
      grid.rowmasks[s->r] |= (1 << number);
      grid.colmasks[s->c] |= (1 << number);
      grid.boxmasks[s->b] |= (1 << number);
	  // here a step by step search of automorphisms
	  // skip puzzle if it is "gangster equivalent" (via relabeling),
      // to a puzzle that has already been checked.
      int depth = s - spots;
      numbers[depth] = number;
      int count = good_map_count[depth];
      if (!count)  {
		if (depth + 1 < pat_cells)   good_map_count[depth + 1] = 0;
      }
      else {
		  unsigned char **map_list = good_maps[depth];
		  unsigned char **new_maps = 0;
          if (depth + 1 < pat_cells)  new_maps = good_maps[depth + 1];
		  for (int n = 0; n < count; n++) {
			  unsigned char *map = *map_list++;
              if (map[number] < number)        goto backtrackdirect;
              if (new_maps && map[number] == number)   *new_maps++ = map;
           }
			  if (new_maps)
				  good_map_count[depth + 1] = new_maps - good_maps[depth + 1];
      }



	  // copy old brute force status and assign number for first 4 given
	  if(gspot<5){
		memcpy(game[gspot].F,game[ispot].F,54*4);
		game[gspot].Seta(number-1,s->cell);
	  }

   }
			  
	if (++s < s_end)      goto next_spot;

	  // skip puzzle if it is "gangster equivalent" 
	  // for rows permutations automorphisms
     { int *s_map = spot_maps[1];
          for (int n = 1; n < p_aut_count; n++) {
             for (int i = 0; i < pat_cells; i++) {
                int d = numbers[s_map[i]];
                if (d < numbers[i])
                   goto backtrack;
                if (d > numbers[i])
                   break;
             }
             s_map += MaxPatCells;
          }
       }
  
   //>>>>>>>>>>>>>>>>> call the last step of the  reduced brute force 
   // do all directly in the last bloc
	memcpy(game[gspot].F,game[4].F,54*4);// last bloc loaded in the final bloc
    for(int i=4;i<gspot;i++){ // load last given brute force 
		game[gspot].Seta(numbers[i]-1,spots[i].cell);
	}
    int ir=game[gspot].DoUpdateR4_9();
	if(!ir)	 goto backtrack; // locked  
	if(ir==2 &&(!game[gspot].IsPatFinalOkR4_9()))	goto backtrack; // not valid	 
	// this is a valid puzzle, send it in output replacing template by numbers		 
	for (int i = 0; i < pat_cells; i++)	buf[spots[i].cell]=numbers[i]+'0';
	cout << buf << endl;// <<<<<<<<<<<<<<<<<<<output
backtrack:
   if (--s < spots)      return;
backtrackdirect:
   {  int number = grcells[s->cell];
      grcells[s->cell] = 0;
      grid.rowmasks[s->r] &= ~(1 << number);
      grid.colmasks[s->c] &= ~(1 << number);
      grid.boxmasks[s->b] &= ~(1 << number);
   }
   if (!s->dmask)      goto backtrack;
   goto next_value;
}


// sorting band 2 and band3 to have a maxlex status
#define SortBand23ToMaxlex \
if (m[0] < m[1]) { int n = m[0]; m[0] = m[1]; m[1] = n; }\
if (m[0] < m[2]) { int n = m[0]; m[0] = m[2]; m[2] = n; }\
if (m[1] < m[2]) { int n = m[1]; m[1] = m[2]; m[2] = n; }\
if (m[3] < m[4]) { int n = m[3]; m[3] = m[4]; m[4] = n; }\
if (m[3] < m[5]) { int n = m[3]; m[3] = m[5]; m[5] = n; }\
if (m[4] < m[5]) { int n = m[4]; m[4] = m[5]; m[5] = n; }\
int n1 = (m[0] << 18) | (m[1] << 9) | m[2];\
int n2 = (m[3] << 18) | (m[4] << 9) | m[5];\
if (band_swap && n1 < n2) { int n = n1; n1 = n2; n2 = n; }

int p_compare(const void *p1, const void *p2)
{
   int res = ((const int *)p2)[0] - ((const int *)p1)[0];
   if (!res)
      res = ((const int *)p2)[1] - ((const int *)p1)[1];
   return res;
}


int Blue_CreatePerms(char * epat){
	int counts[3]={0,0,0};
    for (int i = 0; i < 81; i++)  {
		byte c;
		if(epat[i]<'1' || epat[i]>'9') c=0;
		else c=epat[i]- '0';
        grid[i] = c;
        if (c)  ++counts[TblBoard_Block[i]];
	}
    if (counts[0] != 27) { 
        cerr << "unexpected pattern layout"<<endl;
        return 1;
	}
    band_swap = (counts[1] == counts[2]);
   // generate patterns produced by start & column permutations

   int np = 0;
   int col_p[3];
   for (int stack_p = 0; stack_p < 6; stack_p++)
   for (col_p[0] = 0; col_p[0] < 6; col_p[0]++)
   for (col_p[1] = 0; col_p[1] < 6; col_p[1]++)
   for (col_p[2] = 0; col_p[2] < 6; col_p[2]++) {            
	   int m[6];
       memset(m, 0, sizeof(m));
       int c_order[9];
	   for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
           c_order[3 * i + j] = 3 * p3[stack_p][i] + p3[col_p[i]][j];
 
       for (int i = 0; i < 6; i++) for (int j = 0; j < 9; j++) {
          if (grid[27 + 9 * i + c_order[j]])  m[i] |= 0x100 >> j;
       }
 		SortBand23ToMaxlex;
        patterns[np][0] = n1;
        patterns[np][1] = n2;
        ++np;
    }
    // remove duplicates

    qsort(patterns, 1296, sizeof(patterns[0]), p_compare);
    pattern_count = 1;

    for (int np = 1; np < 1296; np++)   {
            if (patterns[np][0] != patterns[pattern_count - 1][0]
            || patterns[np][1] != patterns[pattern_count - 1][1]) {
               patterns[pattern_count][0] = patterns[np][0];
               patterns[pattern_count][1] = patterns[np][1];
               ++pattern_count;
            }
    }
	bluecount[0]+= pattern_count;
 	return 0;
}


int find_pattern(int n1, int n2){
   int start = -1;
   int end = pattern_count;

   while (end > start + 1)   {
      int n = (start + end) >> 1;

      int res = patterns[n][0] - n1;
      if (!res)     res = patterns[n][1] - n2;

      if (!res)      return n;

      if (res < 0)         end = n;
      else         start = n;
   }

   return -1;
}


 // loop over gangster classes producing <band,pattern> cases
 //  that need be tested ...

void Blue_pair_EDpat_Gang(int n44){

   char buf[256];
   int bp_count = 0;
	memset(p_flags, 0, pattern_count * sizeof(p_flags[0]));

    for (int np = 0; np < pattern_count; np++)      {
		if (p_flags[np])        continue;

        // will need to test pattern 'np' with (gangster) band 'n44'

        int m0[6];
        m0[0] = (patterns[np][0] >> 18) & 511;
        m0[1] = (patterns[np][0] >> 9) & 511;
        m0[2] = patterns[np][0] & 511;
        m0[3] = (patterns[np][1] >> 18) & 511;
        m0[4] = (patterns[np][1] >> 9) & 511;
        m0[5] = patterns[np][1] & 511;

        for (int i = 0; i < 9; i++)  for (int j = 0; j < 9; j++)
                  buf[9 * i + j] = (i < 3 || (m0[i - 3] & (0x100 >> j)))
                     ? ggrids[n44][9 * i + j] : '.';

        buf[81] = 0;
        bp_handler(buf, n44);   // handle <band,pattern> case
        ++bp_count;
 
        // mark equivalent <band,pattern> cases as "handled"

        gangster_data &gt = gtd[n44];

        int *c_order = g_aut_c_order[gt.first_g_aut] + 9;

        for (int k = 1; k < gt.g_aut_count; k++)  {
			int m[6];
            memset(m, 0, sizeof(m));
			for (int i = 0; i < 6; i++)  for (int j = 0; j < 9; j++)  {
                  if (m0[i] & (0x100 >> c_order[j]))
                     m[i] |= 0x100 >> j;
            }

 			SortBand23ToMaxlex;
            p_flags[find_pattern(n1, n2)] = true;
            c_order += 9;
         }
	}
}
